//
//  92. 反转链表II.swift
//  LeetCodeTrain
//
//  Created by rjb on 2021/7/25.
//  Copyright © 2021 rjb. All rights reserved.
//

import Foundation

class Solution92 {
    func reverseBetween(_ head: ListNode?, _ left: Int, _ right: Int) -> ListNode? {
        let newHead = ListNode(-1)
        newHead.next = head
        
        var pre: ListNode? = newHead
        for _ in 0..<left - 1 {
            pre = pre?.next
        }
        
        let cur = pre?.next
        var next: ListNode?
        // 这个地方的头插法
        for _ in 0..<right - left {
            next = cur?.next
            cur?.next = next?.next
            next?.next = pre?.next
            pre?.next = next
        }
        return newHead.next
    }
    
    // 反转链表
    // 反转指定范围的链表
    func reverseBetween2(_ head: ListNode?, _ left: Int, _ right: Int) -> ListNode? {
        let vHead = ListNode(0)
        vHead.next = head
        
        var pre: ListNode? = vHead
        for _ in 0..<left - 1 {
            pre = pre?.next
        }
        
        let cur = pre?.next
        var next: ListNode?
        // 整个的思路是先向后面的节点删除，然后拼接到前面去
        for _ in 0..<right - left {
            next = cur?.next
            cur?.next = next?.next
            next?.next = pre?.next
            pre?.next = next
        }
        return vHead.next
    }
    
    static func test()  {
        let node1 = ListNode(1)
        let node2 = ListNode(2)
        let node3 = ListNode(3)
        let node4 = ListNode(4)
        let node5 = ListNode(5)
        
        node1.next = node2
        node2.next = node3
        node3.next = node4
        node4.next = node5
        
        let solution = Solution92()
        let root = solution.reverseBetween2(node1, 2, 4)
        print(root)
    }
}
